'''
'2': 'abc'
'3': 'def'
'4': 'ghi'
'5': 'jkl'
'6': 'mno'
'7': 'pqrs'
'8': 'tuv'
'9': 'wxyz'
digit string "23"
output ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
'''

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "":
            return []
        s = ["abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        res = [""]
        for d in digits:
            res = [r+c for r in res for c in s[int(d)-2]]
        return res

s = Solution()
print s.letterCombinations("23")
